import java.util.HashMap;

class ListNode{
    public int val;
    public ListNode next;

    public ListNode(int val){
        this.val = val;
    }
    public ListNode(){
    }
}

public class linkTable {
    public ListNode head;
    //      反转链表
//    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    public void reverseList() {
        if (this.head == null){
            return;
        }
//        申请节点 pre和 cur  交换节点tmp
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null){
//            记录当前节点的下一个节点
            tmp = cur.next;
//            然后将当前节点指向pre
            cur.next = pre;
//            pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        this.head = pre;
    }




//    链表的中间结点  快慢双指针做法
//    给定一个头结点为 head 的非空单链表，返回链表的中间结点
//    如果有两个中间结点，则返回第二个中间结点
    public void middleNode() {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null){
//            这里一定要先判断fast != null 不然如果是偶数队列 while执行到最后
//            fast为null 然而有要执行fast.next != null 所以会报空指针异常
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = null;
        this.head = slow;
    }




//    链表中倒数第k个节点 也可以用双指针（快慢指针）做法

//    这段代码有问题 没有关注head为空的情况 下面有另一种
    public void getNodeFromEnd1(int k){
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (k != 0){
            fast = fast.next;
            k--;
        }
        while (fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        this.head = slow;
    }

    public ListNode getNodeFromEnd2(ListNode head,int k){
        if (k<0 || head==null){
            System.out.println("k不合理或者链表为空");
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (k != 0){
            fast = fast.next;
            if (fast == null){
                System.out.println("k不合理");
                return null;
            }
            k--;
        }
        while (fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


//    合并两个有序链表
//    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//    有递归的 方法 但是脑细胞不够
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode pre = head;
        while (list1!=null && list2!=null){
            if (list1.val <= list2.val){
                pre.next = list1;
                pre = pre.next;
                list1 = list1.next;
            }
            else {
                pre.next = list2;
                pre = pre.next;
                list2 = list2.next;
            }
        }
        pre.next = (list1 == null?list2:list1);
        return head.next;
    }


//    链表分割
//    现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前
//    且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
//    解法 使用双指针
    public ListNode partition(ListNode head, int x) {
        // write code here
        ListNode preList = new ListNode(-1);
        ListNode lastList = new ListNode(-1);
        ListNode smallList = preList;
        ListNode bigList = lastList;
        if (head == null){
            return null;
        }
        while (head != null){
            if (head.val <= x){
                smallList.next = head;
                smallList = smallList.next;
                head = head.next;
            }
            else {
                bigList.next = head;
                bigList = bigList.next;
                head = head.next;
            }
        }
        bigList.next = null;
//         bigList.next = null;这个不能省  假设有 1 4 3 2 5 2这6个数 x为3
//         再走的到末尾时 smallList:preList->1->2->2
//                     bigList:lastList->4->5(->2)  注意 这里的5会指向最后一个2 这样会导致在连接的时候造成s循环
        smallList.next = lastList.next;
        return preList.next;
    }



//    删除链表中重复的结点
//    在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
//    例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
    public ListNode deleteDuplication1(ListNode head) {
        if (head == null){
            System.out.println("这是一个空链表");
            return null;
        }
        ListNode pre = new ListNode(-1);
        ListNode cur = new ListNode(-1);
        cur.next = head;
        pre.next = head;
//        可以直接通过cur访问到后面两个的地址/值 并且还能知道cur的地址
        while (cur.next != null && cur.next.next != null){
            if (cur.next.val != cur.next.next.val){
                cur = cur.next;
            }
            else {
                int tmp = cur.next.val;
                while (cur.next != null && cur.next.val == tmp){
                    cur.next = cur.next.next;
                }
            }
        }
        return pre.next;
    }
//      哈希表的方法
    public ListNode deleteDuplication2(ListNode head) {
        if (head == null){
            System.out.println("这是一个空链表");
            return null;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        ListNode cur = new ListNode(-1);
        cur = head;
//        遍历链表统计每个节点值出现的次数
        while (cur != null){
            if (map.containsKey(cur.val)){
                map.put(cur.val, (int)map.get(cur.val)+1);
            }
            else {
                map.put(cur.val, 1);
            }
            cur = cur.next;
        }
        ListNode pre = new ListNode(-1);
        pre.next = head;
        cur = pre;
//        再次遍历链表
        while (cur.next != null){
//            如果节点值计数不为1
            if (map.get(cur.next.val) != 1){
//                删去该节点
                cur.next = cur.next.next;
            }
            else {
//                让cur移动到下一节点
                cur = cur.next;
            }
        }
        return pre.next;
    }





//    链表的回文结构
//    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//    给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

//    思路
//    1.万年不变判断链表是否为空
//    2.找中点：设置两个引用fast、slow从头开始走，fast每次走两个节点，slow每次走一个节点，当fast走到链表尾，slow正好走到链表中点。
//    3.翻转后段链表：设置一个reserveLink方法 将后半部分翻转 将fast = head
//    4.比较fast 和 slow 如果遇到val值不一样的情况，则不是回文，否则是回文。

//    找到中间节点 的reverseCenter方法 如果是偶数返回第一个节点
    public ListNode findCenter(ListNode head){
        if (head == null){
            System.out.println("这是一个空链表");
            return null;
        }
        ListNode fast = new ListNode(-1);
        ListNode slow = new ListNode(-1);
        fast = head;
        slow = head;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
//    翻转链表的方法  上面代码也有一个reverseList方法（反转链表）和他基本一样 重温一遍
    public ListNode reverseLink(ListNode head){
        if (head == null){
            System.out.println("这是一个空链表");
            return null;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null){
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    public boolean chkPalindrome(ListNode head) {
        if (head == null){
            System.out.println("该链表为空");
            return true;
        }
        ListNode lastNode = findCenter(head);
        lastNode = reverseLink(lastNode.next);
        ListNode preNode = head;
        while (lastNode != null){
            if (preNode.val != lastNode.val){
                return false;
            }
            lastNode = lastNode.next;
            preNode = preNode.next;
        }
        return true;
    }



//    160. 相交链表  判断两个链表是否相交
//    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点
//    如果两个链表不存在相交节点，返回 null 。
//    题目数据 保证 整个链式结构中不存在环。
//    注意，函数返回结果后，链表必须 保持其原始结构 。
//    这里没法画图 可以去 看看大佬的思路
//    https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            System.out.println("该链表为空");
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
//        走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。
        while (pA != pB) {
            pA = (pA == null ? headB : pA.next);
            pB = (pB == null ? headA : pB.next);
        }
        return pA;
    }




//    141. 环形链表
//给你一个链表的头节点 head 判断链表中是否有环。
//如果链表中存在 则返回 true 否则返回 false
//    思路及算法  快慢指针  本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解
//    https://leetcode.cn/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
//

    public boolean hasCycle(ListNode head) {
        if (head == null){
            System.out.println("该链表为空");
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;//不同时从一个位置出发 因为使下面的while能够循环
        while (slow != fast){
            if (fast==null || fast.next==null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }



//    142. 环形链表 II
//    给定一个链表的头节点 head返回链表开始入环的第一个节点。如果链表无环，则返回null。
//    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
//    https://leetcode.cn/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
//    思路
//    f=2s （快指针每次2步，路程刚好2倍）
//    f = s + nb (相遇时，刚好多走了n圈）
//    推出：s = nb
//从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
//如何知道slow刚好走了a步 从head开始，和slow指针一起走（都是一步一步走），相遇时刚好就是a步  因为 a + nb一定在入环的第一个节点
    public ListNode detectCycle(ListNode head) {
        if (head == null){
            System.out.println("该链表为空");
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (true){
            if (fast == null || fast.next == null){
                System.out.println("不是环形链表");
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                break;
            }
        }
        fast = head;
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = null;//没这家伙 就死循环了
        return slow;
    }




//输入一个字符串，求出该字符串包含的字符集合，按照字母输入的顺序输出工
//数据范围:输入的字符串长度满足1 < n < 100，且只包含大小写字母，区分大小写.
//本题有多组输入
//输入描述:
//每组数据输入一个字符串，字符申最大长度为100.且只包含字母，不可能为空事，区分大小写。
//输出描述:
//每组数据一行，按字符申原有的字符顺序，输出字符集合，即重复出现并靠后的字母不输出。
//    egg:  输入adsfsdf  输出adsf

//    1.
    public static String func(String str) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < str.length(); i++){
            char ch = str.charAt(i);
            if (!sb.toString().contains(ch+"")){
                sb.append(ch);
            }
        }
        return sb.toString();
    }//main11
//    2.
    public static String func2(String str) {
        int[] array = new int[128];
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (array[ch] == 0){
                sb.append(ch);
                array[ch] = 1;
            }
        }
        return sb.toString();
    }






//下面是链表的一些功能



















    public void createList(){//直接设置
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        ListNode listNode6 = new ListNode(67);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;

        this.head = listNode1;
    }

//    打印链表
    public void display(){
        ListNode cur = this.head;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void display(ListNode link){
        ListNode cur = link;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //    得到单链表的长度
    public int size(){
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //    头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    public void addFirst(ListNode link, int data){
        ListNode node = new ListNode(data);
        node.next = link;
        link = node;
    }
    //    尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if (this.head == null) {
            this.head = node;
        } else {
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }
    public ListNode addLast(ListNode link, int data) {
        ListNode node = new ListNode(data);
        ListNode cur = link;
        if (link == null) {
            return node;
        } else {
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
        return link;
    }
    public ListNode findIndex(int index){
        ListNode cur = this.head;
        while (index-1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //    任意位置插入 第一个数据节点为0下标
    public void addIndex(int index, int data){
        if (index<0 || index>size()){
            System.out.println("插入的位置不合理");
            return;
        }
        if (index == 0){
            addFirst(data);
            return;
        }
        if (index == size()){
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndex(index);
        node.next = cur.next;
        cur.next = node;
    }
    //删除第一次出现关键字为key的节点找前驱的方法
    public ListNode findPre(int key){
        ListNode pre = this.head;
        while (pre.next != null){
            if (pre.next.val == key){
                return pre;
            }
            pre = pre.next;
        }
        return null;
    }
    //    删除第一次出现关键字为key的节点
    public void remove(int key){
//        1.head为空情况下
        if (this.head == null){
            System.out.println("这个单链表为]空");
            return;
        }
//        2.删除第一个情况下
        if (this.head.val == key){
            this.head = this.head.next;
            return;
        }
//        3.找前驱
        ListNode cur = findPre(key);
//        4.删除的节点
        if (cur == null){
            System.out.println("没有你要删除的节点");
            return;
        }
        else {
            ListNode del = cur.next;
            cur.next = del.next;
        }
    }





    //    删除所有值为key的节点
    public ListNode removeAllKey(int key){
        if (this.head == null){
            System.out.println("链表为空");
            return null;
        }
        ListNode pre = this.head;
        ListNode cur = this.head.next;//代表当前需要删除的节点

        while (cur != null){
            if (cur.val == key){
                pre.next = cur.next;
                cur = cur.next;
            }
            else {
                pre = cur;
                cur = cur.next;
            }
        }
        if (this.head.val == key){
            this.head = this.head.next;
        }
        return this.head;
    }


    public void clear(){
//        1.直接的做法
        this.head = null;
//        2.
//        while (this.head != null){
//            ListNode headNext = head.next;
//            this.head.next = null;
//            this.head = headNext.next;
//        }

    }

}

